#include <fstream>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#include "skfrtype.h"
#include "sk_bitfieldsbase.h"
char * empty_puzzle=".................................................................................";


//The cell indexes in each of the 9 rows, 9 columns, and 9 squares out of fss
byte cellsInGroup[27][9] =
{
	{ 0, 1, 2, 3, 4, 5, 6, 7, 8},{ 9,10,11,12,13,14,15,16,17},{18,19,20,21,22,23,24,25,26},
	{27,28,29,30,31,32,33,34,35},{36,37,38,39,40,41,42,43,44},{45,46,47,48,49,50,51,52,53},
	{54,55,56,57,58,59,60,61,62},{63,64,65,66,67,68,69,70,71},{72,73,74,75,76,77,78,79,80},
	{ 0, 9,18,27,36,45,54,63,72},{ 1,10,19,28,37,46,55,64,73},{ 2,11,20,29,38,47,56,65,74},
	{ 3,12,21,30,39,48,57,66,75},{ 4,13,22,31,40,49,58,67,76},{ 5,14,23,32,41,50,59,68,77},
	{ 6,15,24,33,42,51,60,69,78},{ 7,16,25,34,43,52,61,70,79},{ 8,17,26,35,44,53,62,71,80},
	{ 0, 1, 2, 9,10,11,18,19,20},{ 3, 4, 5,12,13,14,21,22,23},{ 6, 7, 8,15,16,17,24,25,26},
	{27,28,29,36,37,38,45,46,47},{30,31,32,39,40,41,48,49,50},{33,34,35,42,43,44,51,52,53},
	{54,55,56,63,64,65,72,73,74},{57,58,59,66,67,68,75,76,77},{60,61,62,69,70,71,78,79,80}
};




class GEN_TABLES{
public:
	GEN_TABLES(){ 
	//============== 
		Genbase(); 	Gen2();	Gen3(); Gen4(); Genpat512();  Genpat72(); 
	}
	void Genbase();
	void Gen2();
	void Gen3();
	void Gen4();
	void Genpat512();
	void Genpat72();
}gen_tables;


// tables generated in the below constructor
int TblMult3[9];  // 3*i
int TblMult9[9];  // 9*i
int TblOtherMask9[9] ; // clear digit in three lines in the column of a block
int Tbldiv3[27]; //i/3 eg :  mini row or digit in F
byte Tblmod3[27];  // i%3
int TblMod9[81]; //i%9 eg : column in block or cell to column
int Tblstartblock[27]; // block offset to first cell
int Tblofftorow[27];// i/9 relative row within a block  (offset to row)
int Tblofftobox[27];//(i%9)/3offset to box
// other bands for a F[i]
byte TblAnother1[27];
byte TblAnother2[27];
int TblBoard_BlockMask27[27]; //1<<i 
int TblRowMask[8];// rows where single  found  000 to 111
word TblShrinkUnsolved[8]; // only unsolved rows
int TblMask26row[9];
// added for canonicalisation on patterns
byte tothers_rc[18][2]={
	{1,2},{0,2},{0,1},  {4,5},{3,5},{3,4},  {7,8},{6,8},{6,7},
	{10,11},{9,11},{9,10},  {13,14},{12,14},{12,13},  {16,17},{15,17},{15,16}};
byte tothers_band [6][2]={{1,2},{0,2},{0,1},
                          {4,5},{3,5},{3,4}};
byte t_units_per_band[6][3]={{0,1,2},{3,4,5},{6,7,8},
						     {9,10,11},{12,13,14},{15,16,17}};
void GEN_TABLES::Genbase(){
	for(int i=0;i<9;i++){
		TblMult3[i] = 3*i;
		TblMult9[i] = 9*i ;
		TblOtherMask9[i]=((1<<i) * Zhoucol) ^ BIT_SET_30;
	}
	for(int i=0;i<27;i++){
		Tbldiv3[i] = i/3;
		Tblmod3[i] = i%3;
		TblMod9[i] = TblMod9[i+27] = TblMod9[i+54] = i%9;
		Tblstartblock[i] = (i%3)*27;
		Tblofftorow[i] = i/9;
		Tblofftobox[i] = (i%9)/3;
		TblAnother1[i]=(i%3)? 3*( i/3 ) :3*( i/3 )+1;
		TblAnother2[i]=(i%3 - 2)?3*( i/3 )+2 :3*( i/3 )+1;
		TblBoard_BlockMask27[i] = (1<<i);
	}
	for(int i=0;i<8;i++){ // bits 25_27  0 to 7
		int rmask=0;  // rows where a single is found
		if(i&1) rmask |= 0x1FF;
		if(i&2) rmask |= (0x1FF<<9);
		if(i&4) rmask |= (0x1FF<<18);
		TblRowMask[i]=rmask ^  BIT_SET_27;

		int rshr=0; // in pointing claiming killl shrinked defined
		if(i&1) rshr |= 7;
		if(i&2) rshr |= (7<<3);
		if(i&4) rshr |= (7<<6);
		TblShrinkUnsolved[i] = rshr;
	}


	for(int i=0;i<9;i++){ // i is the minirow order 0_8
		int w=0x1ff ^ (7<<3*(i%3)); //to kill in the row
		TblMask26row[i]=  (w<<(9*(i/3))) ^ BIT_SET_30;

	}

}

byte Tbloffset[81]; // giving cell to offset in a band
byte TblBoard_Block[81]; // giving cell -> band 

byte TblCelltoBox[81];// relative position in the box
//byte TblaffectedCells[81][20]; // all cells controlled by cell i
byte TblOtherSameBand[27][8]; // cleaning cells other digits

byte BitCount[512] ; // number of bits in a 9 bits value
byte TblBitToInd[512] ; // value 1 to 9 for 1<<n 
byte TblBitIndex[257] ; // value 0 to 8 for 1<<n 
byte Tblfirst0_8[512]; // lowest bit set to 1  bits 1_9
byte TblShrinkMask[512] ;// existing minirows 000 to 111

void GEN_TABLES::Gen2(){
	for(int i=0;i<81;i++){
		Tbloffset[i]=i%27;
		TblBoard_Block[i] =i/27;
		TblCelltoBox[i]=3*((i%27)/9) +i%3 ;
	}

	byte *p=TblOtherSameBand[0];
	for(int i=0;i<27;i++){
		int digit=i/3,blk=i%3;
		for(int j=0;j<9;j++)if(j-digit) (*p++) = (3*j+blk) ;
	}

	for(int i=0;i<512;i++){
		int n=0,po=0;
		for(int j=8;j>=0;j--) if(i &(1<<j)){
			n++; po=j;
		}
		int bti= (n==1)? po+1:0;
		TblBitToInd[i]= bti;
		Tblfirst0_8[i] = po;
		BitCount[i] = n;
		int sh=0;
		if(i& 7) sh+=1;
		if(i&(7<<3)) sh+=2;
		if(i&(7<<6)) sh+=4;
		TblShrinkMask[i] = sh;
	}
	for(int i=0;i<256;i++) TblBitIndex[i]=0;
	for(int i=1;i<9;i++) TblBitIndex[1<<i]=i;
}

int TblComplexMask[512]; // keep mini rows still valid optimised process
int TblKillMask[512]; // killed candidates pointing general
word TblComplexShort[512];  // same as complex  minirows still valid
word TblComplexShortBox[512];
//int TblUniqFlag[8] = {1,1,1,0,1,0,0,0};
word TblNewBoxRow[512]; // new minirow alone in box after shrink
byte TblRowUniq[512] ; // 1 is row not defined in block  mode  to 111
word TblColumnSingleinBox[512];
word TblColumnSingle[512]; // single in column applied to shrinked bloc
word TblShrinkSingle[512] ; // keep only rows with single
int TblMaskSingle[512]; // kill in other blocks locked column /box
int TblMaskDouble[512];// kill for locked in box / column

/*	 7 000 000    9 mini row sequence 
       E00 000    8
	   1C0 000    7
	    38 000    6
	     7 000    5
	       E00    4
	       1C0    3
	        38    2
	         7    1  */
void GEN_TABLES::Gen3(){
	for(int i=0;i<512;i++){
		// pointing claiming in band kill9 initial = already killed
		int shsh=0,kill=0,aigkill=0,ctlrb=0,kill9= i ^  0x1ff,killd=kill9;
		for(int ib=0;ib<3;ib++){ // first locked in boxes
			int iw=i & (0x49<<ib); // shrinked box 1  1..1..1
			if(!BitCount[iw]) {aigkill=1;break;}
			if(BitCount[iw] == 1){
				int imini=Tblfirst0_8[iw],ir=imini/3;
				shsh |= (1<<imini);
				for(int ib2=0;ib2<3;ib2++){ // kill the row
					if(ib==ib2)continue;
					kill |= (7<<(3*ib2))<<(9*ir);
					kill9 |= (1<<ib2)<<(3*ir);
				}
			}
		}
		if(aigkill) TblComplexShortBox[i]=0;
		else TblComplexShortBox[i]=kill9 ^ killd;

		word wnewbr=0,wnewbrw=TblComplexShortBox[i];
		if(wnewbrw) {// see if a new minirow alone appears
			for(int j=0;j<3;j++){
				word boxkill=(7<<(3*j)) & wnewbrw;
				if(!boxkill) continue;
				word newbox= (i &  (7<<(3*j))) ^ boxkill;
				if(BitCount[newbox]==1) wnewbr |= newbox;
			}
		}
		TblNewBoxRow[i]= wnewbr;

		// mask for any killed group of minirows
		int km=0;
		for(int j=0;j<9;j++)
			if((i & (1<<j))) 		km |=( 7 << (3*j));
		TblKillMask[i]=km^BIT_SET_30;

		for(int ir=0;ir<3;ir++){ // now locked in rows 
			int iw=i & (7<<(3*ir));
			if(!BitCount[iw]) {aigkill=1;break;}
			if(BitCount[iw] == 1){
				int imini=Tblfirst0_8[iw],ib=imini%3;
				if(ctlrb & (1<<ib)) {aigkill=1;break;}
				else ctlrb |= (1<<ib);
				shsh |= (1<<imini);
				for(int ir2=0;ir2<3;ir2++){ // kill the box
					if(ir2==ir) continue;
					kill |= (7<<(3*ib))<<(9*ir2);
					kill9 |= (1<<ib)<<(3*ir2);
				}
			}
		}
		if(aigkill) { kill=0; shsh=0;}
		else kill ^=BIT_SET_30;
		//small differences with zhou table, no logic difference
		TblComplexMask[i] = kill; 
		//  find shrinksingles

		int shsing;
		if(!kill || kill==BIT_SET_30){ // shrink must be 0
			shsing=0;
		}
		else{
			shsing= kill9 ^ 0x1ff;
			if(BitCount[shsing & 7 ] - 1) shsing &= 0x1f8;
			if(BitCount[shsing & 0x38 ] - 1) shsing &= 0x1c7;
			if(BitCount[shsing & 0x1c0 ] - 1) shsing &= 0x3f;
		}
		TblShrinkSingle[i] = shsing ;

		if(aigkill) TblComplexShort[i]=0;
		else TblComplexShort[i]=kill9 ^ killd;

		
		int wcols=0;  // TblColumnSingle 
		if(BitCount[i&7] && BitCount[i&0x38] && BitCount[i&0x1c0]){
			if(BitCount[i&7] == 1) wcols |= 0x49;
			if(BitCount[i&0x38] == 1) wcols |= 0x92;
			if(BitCount[i&0x1c0] == 1) wcols |= 0x124;
		}
		TblColumnSingle[i] = wcols;

		int wru=0;  // byte TblRowUniq[512]
		if(!(i&7) ) wru |= 1;
		if(!(i&0x38)) wru |= 2;
		if(!(i&0x1c0)) wru |=4;
		TblRowUniq[i] = wru;

		int killcols=0;
		if(BitCount[i&7] == 1) killcols |= i&7;		
		if(BitCount[i&0x38] == 1) killcols |= i&0x38;  
		if(BitCount[i&0x1c0] == 1) killcols |= i&0x1c0; 
		TblColumnSingleinBox[i]=killcols;

		int killcolsf= ( killcols | (killcols<<9) | (killcols<<18))^BIT_SET_30;
		TblMaskSingle[i] = killcolsf;

		int killcols2=0;
		if(BitCount[i&7] == 2) killcols2 |= i&7;		
		if(BitCount[i&0x38] == 2) killcols2 |= i&0x38;  
		if(BitCount[i&0x1c0] == 2) killcols2 |= i&0x1c0; 
		int killcolsf2= ( killcols2 | (killcols2<<9) | (killcols2<<18))^BIT_SET_30;
		TblMaskDouble[i] = killcolsf2;
	//	if(i==1)
	//		cout<<"ctl  i="<<dec<< i << "  " <<hex<<i
	//		<<  " killcolsf " <<killcolsf<<" TblMaskSingle "<< TblMaskSingle[i] <<endl;
	}}

/* tables to speed up the process bit field to list
   first table is the list of bits for each value of a byte
   second table is an index to the first table

*/

byte tv_string[1024];
word tv_strindex[256];
void GEN_TABLES::Gen4(){
	tv_strindex[0]=0;
	int n=0;
	for(int i=1;i<256;i++){
		for(int j=0;j<9;j++)
			if(i & (1<<j))	tv_string[n++]=j;
		tv_strindex[i]=n;
	}

}

/* tables specific to that location
*/
// tables in use
word tperm6[6][3]={0,1,2, 0,2,1, 1,2,0, 1,0,2, 2,0,1, 2,1,0};
byte tmax3[8]={0,4,4,6,4,6,6,7}; // minirow max pattern 
byte tmin3[8]={0,1,1,3,1,3,3,7}; // minirow min pattern
word maxminirow[512];
word box_col_to_row[512];
word tmax9[512]; // computed table max equivalent to a pattern for row1
word tmin9[512]; // computed table to switch to minilex (in a box for magic40)
byte with_hole[512];
word trowperms[512][1296]; // table of all row possible perms
byte tcrossperms[64][72]; //  perms 2 minirows minlex 
byte tpermsminir1[8][6];  // perms to order box1 on minlex cross 
byte tcolorder[1296][9];
byte tmax9order[512][9]; //same, giving the permutation used 
void GEN_TABLES::Genpat512(){
		// max minirow in a row
	for(int i=0;i<512;i++){
		word wmax=0;
		word wmax9=0,wj[3],wmin[3];
		// max minirow and max form for a row (tmax9)
		for(int j=0;j<3;j++) {
			word w=wj[j]=tmax3[(i>>(3*j) & 7)];
			wmin[j]=tmin3[(i>>(3*j) & 7)];
			if(w>wmax)wmax=w;
		}
		for(int j=0;j<2;j++) for(int k=j+1;k<3;k++){// sort the minirows
			if(wj[j]>wj[k]) {word temp=wj[k]; wj[k]=wj[j]; wj[j]=temp;}
			if(wmin[j]>wmin[k]) {word temp=wmin[k]; wmin[k]=wmin[j]; wmin[j]=temp;}
		}
		maxminirow[i]=wmax;
		tmax9[i]=wj[0] + (wj[1]<<3) + (wj[2]<<6) ;// for test >
		tmin9[i]=wmin[0] + (wmin[1]<<3) + (wmin[2]<<6) ; // for test <
		// set byte to 1 if a hole is in the minirows sequence 
		with_hole[i]=0;
		for(int j=0;j<3;j++){
			word w=wj[j]=(i>>(3*j) & 7);
			if( w < tmax3[w]) {with_hole[i]=1; break;}
		}
		if(wj[0] && (!wj[1]))with_hole[i]=1; 
		// note : wj[2] will never be 0
		// buid trowperms [512][1296]
		int iib[3];
		for(int ib=0;ib<6;ib++) //select box order
			for( iib[0] =0;iib[0]<6;iib[0]++)
				for(iib[1]=0;iib[1]<6;iib[1]++)
					for(iib[2]=0;iib[2]<6;iib[2]++){
						int permnumber=216*ib+36*iib[0]+6*iib[1]+iib[2];
						word & vv= trowperms[i][permnumber];
						vv=0;
						for(int ipb=0;ipb<3;ipb++){
							int box=tperm6[ib][ipb];
							for(int j=0;j<3;j++){// location within a box
								int icol=3*box +  tperm6[iib[ipb]][j];
								if(i&(1<<(icol))) vv |= 1<<(3*ipb+j);
								tcolorder[permnumber][3*ipb+j]=icol;
							}
						}
					}
		// build box row to col  (diagonal morph
		box_col_to_row[i]=0;
		for(int j=0;j<3;j++)for(int k=0;k<3;k++){
			if(i&(1<<(3*j+k))) box_col_to_row[i]|= 1<<(3*k+j);
		}
	}

}
void GEN_TABLES::Genpat72(){
	// build tcrossperms[64][72]
	for(int i=0;i<64;i++){
		int iib[2];
		for(int ib=1;ib<3;ib++) //select box order
			for( iib[0] =0;iib[0]<6;iib[0]++)
				for(iib[1]=0;iib[1]<6;iib[1]++){
					int permnumber=36*(ib-1)+6*iib[0]+iib[1];
					byte & vv= tcrossperms[i][permnumber];
					vv=0;
					int ib2=3-ib;
					for(int j=0;j<3;j++){// location within a box
							int j1= 3*(ib-1)+tperm6[iib[0]][j],
							    j2= 3*(ib2-1)+tperm6[iib[1]][j];
							if(i&(1<<j1)) vv |= 1<<j;
							if(i&(1<<j2)) vv |= 1<<(3+j);
					}
				}

	}// end i
	// build also the small table to order box 1 in crossing magic 40
	// this is a per 3 columns for the minirow value
	for(int i=0;i<8;i++){
		for(int ip=0;ip<6;ip++){
			byte & vv= tpermsminir1[i][ip];
			vv=0;
			for(int j=0;j<3;j++){ 
				if(i&(1<<tperm6[ip][j])) vv |= 1<<j;
			}
		}
	}
//	Buildtmagic40();


}
word tmagicbox1[12]={
	0,1,3,7,012,021,033,035,037,0117,0124,0125
};
// this is optical left to right must be reversed for use 
word tmagic40[50][5]={// serg's 40 magic crossing patterns (no valid puzzle)
	{0117, 0007, 0007, 0111, 0111}, //128
	{0007, 0007, 0117, 0111, 0111}, //129
	{0001, 0007, 0117, 0111, 0117}, //130
	{0021, 0007, 0007, 0111, 0111}, //131
	{0007, 0007, 0117, 0007, 0007}, //132 
	{0001, 0070, 0070, 0007, 0007}, //133 
	{0001, 0111, 0111, 0007, 0007}, //134
	{0001, 0001, 0030, 0002, 0002}, //135
	{0007, 0007, 0007, 0777, 0777}, //137 
	{0000, 0001, 0030, 0012, 0012}, //121  
	{0000, 0007, 0337, 0007, 0007}, //122 
	{0000, 0333, 0777, 0007, 0007}, //123     
	{0000, 0007, 0117, 0007, 0077}, //124
	{0000, 0111, 0333, 0007, 0077}, //125     
	{0000, 0117, 0117, 0007, 0007}, //126
	{0017, 0007, 0007, 0007, 0000}, //102    
	{0007, 0007, 0117, 0077, 0000}, //104
	{0012, 0100, 0100, 0004, 0000}, //108     
	{0003, 0010, 0010, 0007, 0000}, //109
	{0001, 0111, 0777, 0002, 0000}, //110     
	{0001, 0007, 0337, 0002, 0000}, //111
	{0001, 0070, 0171, 0002, 0000}, //112     
	{0001, 0117, 0117, 0002, 0000}, //113
	{0001, 0333, 0333, 0002, 0000}, //114    
	{0001, 0001, 0030, 0012, 0000}, //115
	{0001, 0001, 0030, 0007, 0000}, //116    
	{0001, 0111, 0111, 0077, 0000}, //118
	{0001, 0070, 0070, 0077, 0000}, //119
	{0037, 0007, 0007, 0000, 0000}, //032  
	{0117, 0777, 0777, 0000, 0000}, //138
	{0124, 0777, 0777, 0000, 0000}, //139  
	{0000, 0000, 0777, 0007, 0077}, //098
	{0000, 0000, 0777, 0111, 0117}, //099  
	{0000, 0000, 0333, 0012, 0012}, //100
	{0012, 0111, 0000, 0007, 0000}, //090  
	{0001, 0333, 0000, 0077, 0000}, //092
	{0035, 0111, 0000, 0000, 0000}, //140  
	{0033, 0111, 0000, 0000, 0000}, //141
	{0000, 0000, 0777, 0000, 0777}, //136  
	{0125, 0000, 0000, 0000, 0000}, //004
	//============ added sub patterns not yet in use
	{0000, 0070, 0171, 0002, 0000}, //112   be sure to catch missing 1 box 1   
	{0000, 0001, 0030, 0012, 0000}, //115
	{0000, 0001, 0030, 0002, 0002}, //135
	{0000, 0001, 0030, 0007, 0000}, //116    
	{0013, 0070, 0070, 0000, 0000}, //032  pattern reversing rows 2 3
	{0016, 0070, 0070, 0000, 0000}, //032
	{0000, 0000, 0122, 0007, 0077}, //124
	{0000, 0000, 0122, 0111, 0117}, //130
	{0000, 0000, 0122, 0007, 0007}, //132 
	{0000, 0000, 0122, 0077, 0000}, //104

};


byte patnumber[50]={
	128,129,130,131,132,133,134,135,137,121,
	122,123,124,125,126,102,104,108,109,110,
	111,112,113,114,115,116,118,119, 32,138,
	139, 98, 99,100, 90, 92,140,141,136,  4,
	112,115,135,116, 32, 32,124,130,132,104   

};
byte boxes_5 [9][5]={  // crossing boxes 9 starts
	{0,1,2,3,6}, {1,0,2,4,7}, {2,0,1,5,8},
	{3,4,5,0,6}, {4,3,5,1,7}, {5,3,4,2,8},
	{6,7,8,0,3}, {7,6,8,1,4}, {8,6,7,2,5}
};


int tpat40_sort[50][3] ={// minrow; mincol; pat id
 { 0777000000, 0774774774, 137}, { 060400000, 0220440000, 121},
 { 04400000, 0744740740, 110}, { 04400000, 0774600600, 111},
 { 04400000, 0404770400, 112}, { 04400000, 0774440440, 113},
 { 04400000, 0664660660, 114}, { 0204400000, 044600000, 115},
 { 044600000, 04440000, 135}, { 044600000, 0404400400, 116},
 { 0220440000, 0600600600, 100}, { 06440000, 0404404400, 109},
 { 04770000, 0604600600, 119}, { 04770000, 0444440440, 133},
 { 0772004000, 0772004000, 131}, { 0777004000, 0406404404, 102},
 { 06006000, 0406406400, 141}, { 0777006000, 06006004, 32},
 { 0770400400, 0640640640, 124}, { 0770400400, 0700700700, 99},
 { 0774400400, 0774400400, 130}, { 0777400400, 0444444444, 132},
 { 0777400400, 0604604604, 104}, { 0777400400, 0774004004, 129},
 { 02004400, 02004440, 108}, { 0402404400, 0402404400, 90},
 { 0405406400, 06002004, 140}, { 0770600600, 0440440440, 122},
 { 0604600600, 0444440440, 118}, { 0604600600, 0604600600, 92},
 { 0700700700, 0640640640, 98}, { 0700700700, 0700700700, 136},
 { 0440440440, 0760760760, 123}, { 0440440440, 0770440440, 126},
 { 0444440440, 0444440440, 134}, { 0640640640, 0640640640, 125},
 { 07004004, 0777774774, 138}, { 0777004004, 0777004004, 128},
 { 01002004, 0771772774, 139}, { 05002004, 05002004, 4},
 };

char * t16[416]={
	"6789123789123456","6789123789123465","6789123789123564","6789123789132465",
	"6789123789132546","6789123789132564","6789123789231564","6789123789231645",
	"6789123798132465","6789123798132546","6789123798132564","6789123798213564",
	"6789123798213654","6789123798231564","6789123798231645","6789123897231564",
	"6789123897231645","6789132789123546","6789132789132546","6789132789132564",
	"6789132789213456","6789132789213645","6789132789213654","6789132789231546",
	"6789132789231564","6789132879231564","6789231789123645","6789231789132546",
	"6789231789231564","6789231789312456","6789231798213645","7189236689237145",
	"7189236689237154","7189236689237415","7189236689237451","7189236689237514",
	"7189236689237541","7189236689273145","7189236689273154","7189236689273415",
	"7189236689273451","7189236689273514","7189236689273541","7189236689327145",
	"7189236689327154","7189236689327415","7189236689327451","7189236689327514",
	"7189236689327541","7189236689372145","7189236689372154","7189236689372415",
	"7189236689372451","7189236689372514","7189236689372541","7189236689723145",
	"7189236689723154","7189236689723415","7189236689723514","7189236689723541",
	"7189236689732145","7189236689732154","7189236689732415","7189236689732514",
	"7189236689732541","7189236698237145","7189236698237154","7189236698237415",
	"7189236698237514","7189236698237541","7189236698273145","7189236698273154",
	"7189236698273415","7189236698273514","7189236698273541","7189236698327145",
	"7189236698327154","7189236698327415","7189236698327541","7189236698372145",
	"7189236698372154","7189236698372415","7189236698372514","7189236698372541",
	"7189236698723145","7189236698723154","7189236698723415","7189236698723514",
	"7189236698732145","7189236698732154","7189236698732415","7189236698732514",
	"7189236869237145","7189236869237514","7189236869273145","7189236869273154",
	"7189236869273415","7189236869273514","7189236869327154","7189236869327415",
	"7189236869327514","7189236869372145","7189236869372154","7189236869372415",
	"7189236869372514","7189236869723145","7189236869723154","7189236869723514",
	"7189236869732145","7189236869732154","7189236896237145","7189236896237154",
	"7189236896237514","7189236896273145","7189236896273154","7189236896273514",
	"7189236896327145","7189236896327154","7189236896327514","7189236896372145",
	"7189236896372154","7189236896372514","7189236896723154","7189236896723514",
	"7189236896732154","7189236896732514","7189236968237154","7189236968237514",
	"7189236968273514","7189236968327154","7189236968327514","7189236968372154",
	"7189236968372514","7189236968723154","7189236968732154","7189236986237154",
	"7189236986273154","7189236986327154","7189236986372154","7189263689237145",
	"7189263689237415","7189263689237451","7189263689237514","7189263689273154",
	"7189263689273415","7189263689273451","7189263689273514","7189263689273541",
	"7189263689327154","7189263689327415","7189263689327514","7189263689327541",
	"7189263689372145","7189263689372154","7189263689372415","7189263689372451",
	"7189263689372514","7189263689723145","7189263689723154","7189263689723451",
	"7189263689732145","7189263689732154","7189263689732415","7189263689732451",
	"7189263689732514","7189263689732541","7189263698237154","7189263698237415",
	"7189263698237451","7189263698237514","7189263698273145","7189263698273415",
	"7189263698273451","7189263698273514","7189263698327145","7189263698327154",
	"7189263698327415","7189263698327451","7189263698327514","7189263698372154",
	"7189263698372415","7189263698372514","7189263698372541","7189263698732145",
	"7189263698732154","7189263698732451","7189263869237154","7189263869237415",
	"7189263869237514","7189263869273451","7189263869327415","7189263869327451",
	"7189263869327514","7189263869372145","7189263869372154","7189263869372514",
	"7189263896237145","7189263896237154","7189263896237451","7189263896327145",
	"7189263896327154","7189263896327415","7189263896327451","7189263896327514",
	"7189263896327541","7189263896372145","7189263896372154","7189263896372451",
	"7189263968327145","7189263968327154","7189263968327415","7189263968327514",
	"7189263968327541","7189263968372145","7189263986327145","7189263986327154",
	"7189263986327451","7189326689237451","7189326689237514","7189326689237541",
	"7189326689273145","7189326689273451","7189326689273541","7189326689327154",
	"7189326689327451","7189326689327541","7189326689372415","7189326689372541",
	"7189326689723145","7189326689723415","7189326689732145","7189326689732415",
	"7189326689732514","7189326689732541","7189326698237145","7189326698237541",
	"7189326698273514","7189326698273541","7189326698732415","7189326869372514",
	"7189623689237145","7189623689237154","7189623689273145","7189623689273154",
	"7189623689273541","7189623689327145","7189623689327154","7189623689372145",
	"7189623689372154","7189623689372514","7189623689723145","7189623689723154",
	"7189623689723415","7189623689723451","7189623689723514","7189623689723541",
	"7189623689732145","7189623689732154","7189623689732415","7189623689732451",
	"7189623689732514","7189623689732541","7189623698237145","7189623698237154",
	"7189623698237541","7189623698273145","7189623698273154","7189623698327145",
	"7189623698327154","7189623698327514","7189623698372145","7189623698372154",
	"7189623698732145","7189623698732154","7189623698732415","7189623698732514",
	"7189623698732541","7189623869237145","7189623869273145","7189623869273154",
	"7189623869273451","7189623869327154","7189623869372145","7189623869372154",
	"7189623896237145","7189623896237154","7189623896237415","7189623896237451",
	"7189623896237514","7189623896237541","7189623896327145","7189623896327154",
	"7189623896327415","7189623896327451","7189623896327514","7189623896372145",
	"7189623896372154","7189623896372451","7189623968327145","7189623968327154",
	"7189623968327415","7189623968372145","7189623968372154","7189623986327145",
	"7189623986327154","7189623986327415","7189623986327451","7189623986327514",
	"7189623986327541","7189632689237145","7189632689273145","7189632689273154",
	"7189632689273514","7189632689327154","7189632689372145","7189632689372154",
	"7189632689723145","7189632689723514","7189632689732145","7189632689732154",
	"7189632689732514","7189632689732541","7189632698237145","7189632698237154",
	"7189632698237514","7189632698273145","7189632698327145","7189632698327154",
	"7189632698327541","7189632698372154","7189632698732145","7189632698732514",
	"7189632869273145","7189632869372145","7189632896237145","7189632896237415",
	"7189632896327145","7189632896327154","7189632896327451","7189632896327541",
	"7189632896372145","7189632896372154","7189632896372451","7189632968327145",
	"7189632968327154","7189632968327451","7189632986327145","7289163689173452",
	"7289163689713254","7289163698137425","7289163698137524","7289163698317254",
	"7289163698317524","7289163698713254","7289163869713245","7289163869731245",
	"7289163869731524","7289163896317245","7289163896731524","7289613689173245",
	"7289613689713245","7289613689713254","7289613698137254","7289613698317245",
	"7289613698317254","7289613698713245","7289613869713245","7289613869731245",
	"7289613869731254","7289613896137245","7289613896137254","7289613896317245",
	"7289613896317425","7289613896731245","7289613896731254","7289613968137245",
	"7289613968137254","7289613968731245","7289613986137245","7289631689173245",
	"7289631689713254","7289631698317254","7289631869713245","7289631869713254",
	"7289631869731245","7289631869731254","7289631896137245","7289631896137254",
	"7289631896137425","7289631896317245","7289631896317254","7289631896731245",
	"7289631968137254","7289631968731245","7289631986137245","7389612896127354",
	"7389612896172354","7389612896271354","7389612896721354","7389621896217354",
	"7893612986217354","7289631968731254","7289631986137254","7893612896127345",
	"7893612896127354","7893612896217354","7389612896127345","7389612896172345",
	"7389612896271345","7389612896217345","7389612896217354","7389612896712354",
	"7389612986172354","7389612986217354","7389621896127345","7389621986127354",
};

char * t44gang[44]={
"123456789456789123789123456","123456789456789123789123465","123456789456789123789123564","123456789456789123789132465",
"123456789456789123789132546","123456789456789123789132564","123456789456789123789231564","123456789456789123789231645",
"123456789456789123798132546","123456789456789123798213564","123456789456789123798213654","123456789456789123798231564",
"123456789456789123798231645","123456789456789123897231564","123456789456789132789123546","123456789456789132789213456",
"123456789456789132789213645","123456789456789132789213654","123456789456789132789231546","123456789456789231789123645",
"123456789456789231789312456","123456789457189236689273145","123456789457189236689273154","123456789457189236689273514",
"123456789457189236689372145","123456789457189236689372154","123456789457189236698237514","123456789457189236698723145",
"123456789457189236698732145","123456789457189236869372145","123456789457189263689273154","123456789457189263689723154",
"123456789457189263689732154","123456789457189263968327145","123456789457189263968327514","123456789457189263968372145",
"123456789457189263986327145","123456789457189263986327154","123456789457189623689723145","123456789457189623689723154",
"123456789457189623689723514","123456789457189632698732514","123456789457189632896372154","123456789457289631896137254",
};

word t416to44[416]={
0,1,2,3,4,5,6,7,3,8,8,9,10,11,12,13,6,14,4,5,15,16,17,18,12,9,
19,17,7,20,10,6,5,6,5,12,12,21,22,21,22,23,23,16,8,16,8,5,5,24,25,24,
25,23,23,16,5,16,8,8,21,8,21,9,9,18,8,18,26,26,10,23,10,12,12,9,9,9,
22,23,23,23,7,7,27,12,27,26,28,5,28,22,12,27,9,21,9,10,21,23,28,29,24,29,
23,12,6,18,23,16,12,16,27,9,21,10,23,21,28,29,24,23,6,18,16,9,8,26,12,9,
22,23,7,12,5,5,22,8,25,12,12,18,6,30,26,30,28,28,8,16,5,5,24,25,24,25,
23,17,31,31,9,32,9,32,21,21,11,9,11,24,27,27,21,27,11,11,11,11,25,21,21,12,
12,12,21,21,10,9,21,18,21,23,22,24,9,12,27,24,24,21,21,21,21,26,26,11,24,24,
33,29,33,34,34,35,36,37,37,5,7,7,12,5,7,3,3,5,27,12,5,5,27,27,12,12,
10,23,23,23,23,10,7,5,22,31,22,5,3,21,8,9,38,39,38,39,40,40,23,37,23,37,
24,24,12,9,24,27,27,9,8,21,21,12,23,23,23,35,35,23,34,32,32,5,24,9,28,32,
28,32,34,34,22,31,22,31,22,21,27,27,24,37,24,35,23,40,39,40,39,38,38,12,21,26,
21,8,9,32,37,36,23,37,24,24,17,5,26,16,5,12,27,28,38,41,24,29,17,17,38,26,
26,28,37,42,42,26,27,27,31,20,41,25,33,33,33,35,32,24,33,24,13,41,26,40,24,24,
36,21,31,16,21,31,25,40,41,16,11,18,10,10,30,35,42,24,27,27,21,16,26,43,42,22,
25,6,4,30,18,5,17,16,8,8,3,4,15,0,1,3,2,14,19,14,4,15,17,4,5,1,
};